package alo.p11.work;

/**
 * @ClassName BinarySearchRotated
 * @Description 经过转换的数组中找一个元素[15 16 19 20 25 1 3 4 5 7 10 14]
 * @Author Fanxc
 * @DATE 2021/3/14 9:23
 * @Version 1.0
 */
public class BinarySearchRotated {

    int findPivot(int[] A,int start,int finish){
        if (finish-start==0){
            return start;
        }else if (start==finish-1){
            return A[start]>=A[finish]?start:finish;
        }else {
            int mid=start+(finish-start)/2;
            if (A[start]>A[mid]){
                return findPivot(A,start,mid);
            }else return findPivot(A,mid,finish);
        }
    }

    int binarySearch(int[] A,int low,int high,int x){
        if (high>=low){
            int mid=low+(high-low)/2;
            if (x==A[mid]){
                return mid;
            }else if (x>A[mid]){
                return binarySearch(A,mid+1,high,x);
            }else return binarySearch(A,low,mid-1,x);
        }
        return -1;
    }

    int Search(int[] A,int n,int x){
        int pivot=findPivot(A,0,n-1);
        if (A[pivot]==x){
            return pivot;
        }
        if (A[pivot]>x&&x<A[0]){
            return binarySearch(A,0,pivot-1,x);
        }else if (x>A[pivot+1]&&x<A[n-1]){
            return binarySearch(A,pivot+1,n-1,x);
        }else return -1;
    }





    int binarySearchRotated(int[] A,int start,int finish,int data){
        if (start>finish){
            return -1;
        }
        int mid=start+(finish-start)/2;
        if (data==A[mid]){
            return mid;
        }else if (A[start]<=A[mid]){
            if (data>=A[start]&&data<A[mid]){
                return binarySearchRotated(A,start,mid-1,data);
            }else return binarySearchRotated(A,mid+1,finish,data);
        }else {
            if (data>A[mid]&&data<A[finish]){
                return binarySearchRotated(A,mid+1,finish,data);
            }else return binarySearchRotated(A,start,mid-1,data);
        }
    }
}
